package com.dh.leetcode.k1;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * ClassName: _1743_restore_the_array_from_adjacent_pairs
 *
 * @author shouzimu
 * @Description: 1743. 从相邻元素对还原数组
 * 存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
 * <p>
 * 给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。
 * <p>
 * 题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。
 * <p>
 * 返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：adjacentPairs = [[2,1],[3,4],[3,2]]
 * 输出：[1,2,3,4]
 * 解释：数组的所有相邻元素对都在 adjacentPairs 中。
 * 特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。
 * 示例 2：
 * <p>
 * 输入：adjacentPairs = [[4,-2],[1,4],[-3,1]]
 * 输出：[-2,4,1,-3]
 * 解释：数组中可能存在负数。
 * 另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。
 * 示例 3：
 * <p>
 * 输入：adjacentPairs = [[100000,-100000]]
 * 输出：[100000,-100000]
 * <p>
 * https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/
 * @date 2021/7/25 21:57
 */
public class _1743_restore_the_array_from_adjacent_pairs {

    /**
     * 查看题解了，找到数组第一个元素，即只有一个相邻的元素
     * <p>
     * 后面的找法为找到只有一个相邻的元素
     * <p>
     * 如[[4,-2],[1,4],[-3,1]]
     * 第一次找出1
     * 第二次相邻为2
     * 和2相邻的有1和3，1已经添加，所以下一个元素为3
     *
     * @param adjacentPairs
     * @return
     */
    public int[] restoreArray(int[][] adjacentPairs) {
        int length = adjacentPairs.length + 1;
        Map<Integer, Set<Integer>> map = new HashMap<>(length);
        Set<Integer> firstSet = new HashSet<>();

        for (int[] adjacentPair : adjacentPairs) {
            int a0 = adjacentPair[0];
            int a1 = adjacentPair[1];
            Set<Integer> set0 = map.getOrDefault(a0, new HashSet<>());
            set0.add(a1);
            map.put(a0, set0);

            Set<Integer> set1 = map.getOrDefault(a1, new HashSet<>());
            set1.add(a0);
            map.put(a1, set1);

            boolean add = firstSet.add(a0);
            if (!add) {
                firstSet.remove(a0);
            }
            add = firstSet.add(a1);
            if (!add) {
                firstSet.remove(a1);
            }
        }
        int first = 0;
        for (Integer integer : map.keySet()) {
            if (map.get(integer).size() == 1) {
                first = integer;
                break;
            }
        }
        int[] res = new int[length];
        res[0] = first;
        int preview = first;
        Set<Integer> set = map.get(first);
        first = set.iterator().next();
        res[1] = first;
        map.get(first).remove(preview);

        for (int i = 2; i < length; i++) {
            set = map.get(first);
            preview = first;
            first = set.iterator().next();
            res[i] = first;
            map.get(first).remove(preview);
        }
        return res;

    }

    @Test
    public void restoreArrayTest() {
        Assert.assertEquals(Arrays.toString(new int[]{1, 2, 3, 4}), Arrays.toString(restoreArray(new int[][]{{2, 1}, {3, 4}, {3, 2}})));
        Assert.assertEquals(Arrays.toString(new int[]{-2, 4, 1, -3}), Arrays.toString(restoreArray(new int[][]{{4, -2}, {1, 4}, {-3, 1}})));
    }
}
